/*************************************************************************
	> File Name: 014.P1144.最短路计数.cpp
	> Author: Maureen 
	> Mail: Maureen@qq.com 
	> Created Time: 五  6/25 16:47:41 2021
 ************************************************************************/

#include <iostream>
#include <cstring>
#include <queue>
using namespace std;

//Dijkstra + 链式前向星

struct edge {
    int e, v, next; //边的终点、权值
};

struct node {
    int id, dis; //当前点的编号，dis到该点为止的距离
    bool operator<(const node &b) const {
        return this->dis > b.dis;
    }
};


edge edg[4000005]; //边集，因为是双向边
int n, m, edg_cnt, ans[1000005], ans_cnt[1000005], head[1000005]; //ans_cnt记录最短路的方案数

void add_edg(int a, int b) {
    edg[edg_cnt].e = b;
    edg[edg_cnt].v = 1;
    edg[edg_cnt].next = head[a];
    head[a] = edg_cnt++;
}

int main() {
    memset(ans, 0x3f, sizeof(ans));
    memset(head, -1, sizeof(head));
    cin >> n >> m;
    for (int i = 0; i < m; i++) {
        int a, b;
        cin >> a >> b;
        add_edg(a, b); //加边a->b
        add_edg(b, a); //加边b->a
    }
    priority_queue<node> que;
    que.push((node){1, 0}); //起始起点状态加入优先队列
    ans[1] = 0; //起点的最短路
    ans_cnt[1] = 1; //起点的方案数
    while (!que.empty()) {
        node temp = que.top();
        que.pop();
        if (temp.dis > ans[temp.id]) { //去重判断，该种状态对应的不是答案
            continue;
        }
        for (int i = head[temp.id]; i != -1; i = edg[i].next) { //遍历以temp.id这个点为起点的所有边
            int e = edg[i].e; 
            if (ans[e] > ans[temp.id] + 1) { //这条边终点对应的答案 大于 这条边起点对应的答案+边的权值，说明最短路被更新了
                ans[e] = ans[temp.id] + 1; //更新最短路
                ans_cnt[e] = ans_cnt[temp.id]; //更新点对应的最短路数量
                que.push((node){e, ans[e]}); //新点放入优先队列
            } else if (ans[e] == ans[temp.id] + 1) { //最短路长度相等，最短路不会被更新，方案数被更新
                ans_cnt[e] += ans_cnt[temp.id]; //更新方案数
                ans_cnt[e] %= 100003;
            }
        }
    }

    for (int i = 1; i <= n; i++) { //输出从1号点到每个点的方案数
        cout << ans_cnt[i] << endl;
    }

    return 0;
}
